/*
prim算法，克鲁斯卡尔算法
将图中所给的点用所给的边连接起来，所得到的树的权值最小
求连通图的最小生成树
如果该图中有n个节点，那么它需要n-1条边
那么任务就是在边集中找出n-1条边，将所有节点连接起来使得它的代价最小
树的特点：
    没有回路且连通

克鲁斯卡尔算法的思想：（向T集合中加入n-1边）
    按边的权值从小到大排列后， 向E集合中按照顺序加入边， 加入的边不能构成回路，如果构成了回路，则继续选择，直到选出n-1条边
    不考虑选择过的边
Prim算法的思想:（向集合中加入n个点）
    选择一个节点，加入点集S，然后选择一条与该节点相连的边（该边是权值最小的），如果该边加入后没有构成回路，则将改变加入边集合 E,
    将该边相关的另一个节点加入点集，接下来选择一条点集中的点所关联边中最小的一条边，进行判断，加入还是不加入边集合
    如果该边加入后构成回路，则选择另一条权值较小的边，再进行判断，直到加入n个点

*/

/*
单源最短路径的算法(迪杰斯特拉算法)
从源点到终点的最短路径问题
给定带权有向图G= (V,E)
每条边的权值为e = <i,j> = w(e) 表示从i到j的距离
源点为s 求它到其他节点的最短路径

设定一个集合S 若x是属于S的，则说明x到源点s的最短路径长度已知
初始情况：S={s}
最终目标：S=V  即求得源点到所有点的集合
初始化：相连接的点置为权值，path表置为可达标记，不相连的置为正无穷，path置不可达标记
从s到u 相对于S的最短路径： 从s到u且仅经过S中的顶点的最短路径

dist[u]  从s到u相对于S的最短路径长度
加入一个点
short[u] 从s到u的

*/
#include <iostream>
#include <cstring>

using namespace std;

const int MAXV=100;
const int INF = 0x3f3f3f;
typedef struct MatGraph
{
    int edges[MAXV][MAXV];
    int n,e;
};
void Dijkstra(MatGraph g, int v)  //v表示的是源点
{
    int dist[MAXV],path[MAXV];
    int S[MAXV];
    int MINdis,i,j,u;
    //根据邻接矩阵进行初始化
    for(i=0;i<g.n;i++)
    {
        dist[i] = g.edges[v][i];
        S[i] = 0; //S[]置空
        if(g.edges[v][i]<INF)
            path[i] = v; //源点到该节点是可达的
        else
            path[i] = -1; //不可到达
    }
    S[v] = 1; //源点编号放入S中
    path[v] = 0;
    //循环直到所有点的最短路径求出
    for(i=0;i<g.n-1;i++)
    {
        MINdis = INF;//置最大长度为初值
        for(j=0;j<g.n;j++)
        {
            if(S[j]==0 && dist[j]<MINdis)  //选取不在S中的点，且具有最短长度的顶点u
            {
                u = j;
                MINdis = dist[j];
            }
        }
        S[u] = 1; //将顶点u加入点集合S中
        //修改不在点集合中的其他点的最短路径
        for(j=0;j<g.n;j++)
        {
            if(S[j] == 0)
                if(g.edges[u][j]<INF && dist[u]+g.edges[u][j]<dist[j])
                {
                    dist[j] = dist[u]+g.edges[u][j];
                    path[j] = u;
                }
        }

    }
    Display(g,dist,path,S,v);
}

void Display(MatGraph g, int dist[],int path[], int S[],int v)
{
    //输出从顶点v出发的所有最短路径
    int i,j,k;
    int apath[MAXV],d;
    for(i=0;i<g.n;i--)
    {
        if(S[i]==1 && i!=v)
        {
            d=0;
            apath[d]=i; //apath是用于保存从源点到点i的最短路径的 
            k=path[i];
            if(k==-1)
                cout<<'没有路径';
            else
            {
                while(k!=v) //对path表进行反向追溯的过程
                {
                    d++;
                    apath[d] = k; //当前节点到达源点路上的前一个节点
                    k = path[k];
                }
                d++;
                apath[d] = v;  //路径的起点
                cout<<apath[d];  //输出路径的起点
                for(j=d-1;j>=0;j--)  //输出其他顶点 反向输出
                    cout<<apath[j];
            }

        }
    }
}